// bitmap.c 
//	Routines to manage a bitmap -- an array of bits each of which
//	can be either on or off.  Represented as an array of integers.
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "bitmap.h"

int CheckArray[32];
//----------------------------------------------------------------------
// BitMap::BitMap
// 	Initialize a bitmap with "nitems" bits, so that every bit is clear.
//	it can be added somewhere on a list.
//
//	"nitems" is the number of bits in the bitmap.
//----------------------------------------------------------------------

BitMap::BitMap(int nitems) 
{ 
    numBits = nitems;
    numWords = divRoundUp(numBits, BitsInWord);
    map = new unsigned int[numWords];
    for (int i = 0; i < numBits; i++) 
        Clear(i);
}

//----------------------------------------------------------------------
// BitMap::~BitMap
// 	De-allocate a bitmap.
//----------------------------------------------------------------------

BitMap::~BitMap()
{ 
    delete map;
}

//----------------------------------------------------------------------
// BitMap::Set
// 	Set the "nth" bit in a bitmap.
//
//	"which" is the number of the bit to be set.
//----------------------------------------------------------------------

void
BitMap::Mark(int which) 
{ 
    ASSERT(which >= 0 && which < numBits);
    map[which / BitsInWord] |= 1 << (which % BitsInWord);
}
    
//----------------------------------------------------------------------
// BitMap::Clear
// 	Clear the "nth" bit in a bitmap.
//
//	"which" is the number of the bit to be cleared.
//----------------------------------------------------------------------

void 
BitMap::Clear(int which) 
{
    ASSERT(which >= 0 && which < numBits);
    map[which / BitsInWord] &= ~(1 << (which % BitsInWord));
}

//----------------------------------------------------------------------
// BitMap::Test
// 	Return TRUE if the "nth" bit is set.
//
//	"which" is the number of the bit to be tested.
//----------------------------------------------------------------------

bool 
BitMap::Test(int which)
{
    ASSERT(which >= 0 && which < numBits);
    
    if (map[which / BitsInWord] & (1 << (which % BitsInWord)))
	return TRUE;
    else
	return FALSE;
}

//----------------------------------------------------------------------
// BitMap::Find
// 	Return the number of the first bit which is clear.
//	As a side effect, set the bit (mark it as in use).
//	(In other words, find and allocate a bit.)
//
//	If no bits are clear, return -1.
//----------------------------------------------------------------------

int 
BitMap::Find() 
{
    for (int i = 0; i < numBits; i++)
	if (!Test(i)) {
	    Mark(i);
	    return i;
	}
    return -1;
}

//----------------------------------------------------------------------
// BitMap::NumClear
// 	Return the number of clear bits in the bitmap.
//	(In other words, how many bits are unallocated?)
//----------------------------------------------------------------------

int 
BitMap::NumClear() 
{
    int count = 0;

    for (int i = 0; i < numBits; i++)
	if (!Test(i)) count++;
    return count;
}

//----------------------------------------------------------------------
// BitMap::Print
// 	Print the contents of the bitmap, for debugging.
//
//	Could be done in a number of ways, but we just print the #'s of
//	all the bits that are set in the bitmap.
//----------------------------------------------------------------------
//
// changed for a more proper printout
// jpj9668
void
BitMap::Print() 
{
    printf("\nBitmap set:\n"); 
    for (int i = 0; i < numBits; i++)
	{
		if(Test(i) == TRUE)
		{
			printf("1");
		}
		else
		{
			printf("0"); 
		};
	};
    printf("\n");
}
//---------------------------------------------
// BitMap::CheckEmptyArray
// is used to create an array with the size
// of the hole in mainMemory. The size is located in
// it's first position
//------------------------------------------
void
BitMap::CheckEmptyArray()
{
	Print();
	int count = 0;
	int offsetCount = 0;
	for(int j =0; j < numBits; j++)
	{
		CheckArray[j] = 0;
	};
	//for(int b = 0; b < 5; b++)
	//{
	//	Mark(b);
	//};
	// go through checkarray and find holes
	// record the holes in first position of the 
	// hole in mainMemory
	for(int b = 0; b < numBits;b++)
	{
		if(Test(b) == FALSE)
		{
			for(int p = b;p<numBits;p++)
			{
				if(Test(p) == FALSE)
				{
					count++;
					//printf("count++ = %d",count);
					offsetCount = p;
					//printf("offsetCount = %d",offsetCount);
					if(offsetCount == 31)
					{
						CheckArray[b] = count;
					};
				}
				else if(Test(p) == TRUE)
				{
					p=(numBits);
					CheckArray[b] = count;
				}
				
			};
		};
		b = b + offsetCount;
		offsetCount = 0;
	};
	//for(int j =0; j < numBits; j++)
	//{
	//	printf("CheckArray[j] = %d \n",CheckArray[j]);
	//};
}				
//---------------------------------------------
// BitMap::FirstFitFunc()
// This function will return the position of 
// the first position in mainMemory that will
// have room for the entire process
//---------------------------------------------
int
BitMap::FirstFitFunc(int size)
{
	int FirstFitNumber = 0;
	for(int i = 0; i < numBits; i++)
	{
		if (CheckArray[i] >= size)
		{
			FirstFitNumber = i;
			return FirstFitNumber;
		};
	};
	// here its needs a system call 
	return -1;
}

//---------------------------------------------
// BitMap::BestFitFunc()
// This function will return the position of 
// the first position in mainMemory that will
// have room for the entire process. The size of
// this hole must be the best fit for the 
// process
//---------------------------------------------
int
BitMap::BestFitFunc(int size)
{
	////int checkForEmptyCount = 0;
	//int BestFitArray = 0;
	int BestFitNumber = 0;
	for(int b = 0; b < numBits; b++)
	{
		if(CheckArray[b] == size)
		{
			BestFitNumber = b;
			return BestFitNumber;
		};
	};
	return BestFitNumber;
		//else if(Check///
// unfinished due to join
}
	

// These aren't needed until the FILESYS assignment

//	----------------------------------------------------------------------
// BitMap::FetchFromFile
// 	Initialize the contents of a bitmap from a Nachos file.
//
//	"file" is the place to read the bitmap from
//----------------------------------------------------------------------

void
BitMap::FetchFrom(OpenFile *file) 
{
    file->ReadAt((char *)map, numWords * sizeof(unsigned), 0);
}

//----------------------------------------------------------------------
// BitMap::WriteBack
// 	Store the contents of a bitmap to a Nachos file.
//
//	"file" is the place to write the bitmap to
//----------------------------------------------------------------------

void
BitMap::WriteBack(OpenFile *file)
{
   file->WriteAt((char *)map, numWords * sizeof(unsigned), 0);
}
